477D - Dreamoon and Binary - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb(x) push_back(x)
#define FI first
#define SE second
#define maxeq(x, y) (x) = max((x), (y))
#define mineq(x, y) (x) = min((x), (y))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int mod1 = 1000000007, mod2 = 1000000033, mod = 1000000007;
pair<unsigned, unsigned> hasz[5002][5002];

int32_t ile[5002][5002], mini[5002][5002];
int pot[5002];

pii nhasz(pii hasz, char c) {
    hasz.FI *= 2;
    hasz.FI += c - '0';
    hasz.FI %= mod1;
    hasz.SE *= 2;
    hasz.SE += c - '0';
    hasz.SE %= mod2;
    return hasz;
}

bool mniejszy(int i, int j, int d, string &slo) {
//    if (hasz[i][d] == hasz[j][d])
//        return false;
//    if (slo[i] > slo[j])
//        return true;
    int p = 0, k = d-1;
    while (p < k) {
        int s = (p+k)/2;
        if (hasz[i][s] == hasz[j][s]) {
            p = s + 1;
        } else {
            k = s;
        }
    }
//    cout << i << " " << j << " " << d << " " << p << "\n";
    return slo[i+p] < slo[j+p];
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string slo;
    cin >> slo;
    int n = slo.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            hasz[i][j-i] = nhasz(hasz[i][max(j-i-1, 0ll)], slo[j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        pot[i] = pot[i-1] * 2 % mod;
        ile[0][i] = 1;
        mini[i][0] = 1000000001;
    }
    ile[0][0] = 1;
    mini[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ile[i][j] = ile[i][j-1];
            mini[i][j] = mini[i][j-1];
            if (slo[i-j] == '1') {
                if (i >= 2 * j && !mniejszy(i - j, i - 2 * j, j, slo)) {
                    //cout << i << " " << j << "row\n";
                    ile[i][j] += ile[i - j][j];
                    mineq(mini[i][j], mini[i - j][j] + 1);
                } else if (j <= i) {
                    //cout << i << " " << j << "mn\n";
                    ile[i][j] += ile[i - j][j - 1];
                    mineq(mini[i][j], mini[i - j][j - 1] + 1);
                }
            }
            ile[i][j] %= mod;
            //cout << i << " " << j << " " << ile[i][j] << "\n";
        }
    }
    cout << ile[n][n] << "\n";
    int bestmini = 1000000000000000001ll;
    for (int i = 1; i <= n; i++) {
        if (i >= 20 && bestmini < mod) {
            break;
        }
        int res = 0;
        for (int j = n - i + 1; j <= n; j++) {
            res *= 2;
            res += slo[j - 1] - '0';
            res %= mod;
        }
        //cout << i << " " << res << " " << mini[n][i] << "\n";
        if (mini[n][i] == 1000000001)
            continue;
        mineq(bestmini, res + mini[n][i]);
    }
    cout << bestmini << "\n";
}